package com.algorithm.heap;

import java.util.ArrayList;
import java.util.List;

/**
 * 堆数据结构
 * 
 * @author quanwei
 * 
 * @param <T>
 */
public class Heap<T extends Comparable<T>> {
	/**
	 * 最大N个记录
	 * 
	 * @param data
	 * @param n
	 * @return
	 */
	public List<T> maxN(T[] data, int n) {
		return topN(data, n, true);
	}

	/**
	 * 最小N个记录
	 * 
	 * @param data
	 * @param n
	 * @return
	 */
	public List<T> minN(T[] data, int n) {
		return topN(data, n, false);
	}

	/**
	 * 排序-升序
	 * 
	 * @param data
	 */
	public void sort(T[] data) {
		_build(data, data.length, true);
		_sort(data, data.length, true);
	}

	/**
	 * 排序-降序
	 * 
	 * @param data
	 */
	public void rsort(T[] data) {
		_build(data, data.length, false);
		_sort(data, data.length, false);
	}

	/**
	 * 建堆
	 * 
	 * @param data
	 * @param max
	 */
	public void build(T[] data, boolean max) {
		_build(data, data.length, max);
	}

	/**
	 * 输出推结构
	 * 
	 * @param data
	 */
	public void printr(T[] data) {
		printr(data, data.length);
	}

	protected List<T> topN(T[] data, int n, boolean max) {
		if (n > data.length) {
			n = data.length;
		}

		_build(data, n, !max);
		for (int i = n; i < data.length; i++) {
			if (max) {
				if (data[i].compareTo(data[0]) > 0) {
					swap(data, 0, i);
					heapify(data, n, 0, !max);
				}
			} else {
				if (data[i].compareTo(data[0]) < 0) {
					swap(data, 0, i);
					heapify(data, n, 0, !max);
				}
			}
		}

		// 排序
		_build(data, n, !max);
		_sort(data, n, !max);
		List<T> result = new ArrayList<T>();
		for (int i = 0; i < n; i++) {
			result.add(data[i]);
		}

		return result;
	}

	protected void _build(T[] data, int len, boolean max) {
		for (int i = (len - 1) / 2; i >= 0; i--) {
			heapify(data, len, i, max);
		}
	}

	protected void heapify(T[] data, int len, int i, boolean max) {
		int l = left(data, i);
		int r = right(data, i);
		int m = i;

		if (max) {
			if (l < len && data[l].compareTo(data[m]) > 0) {
				m = l;
			}
			if (r < len && data[r].compareTo(data[m]) > 0) {
				m = r;
			}
		} else {
			if (l < len && data[l].compareTo(data[m]) < 0) {
				m = l;
			}
			if (r < len && data[r].compareTo(data[m]) < 0) {
				m = r;
			}
		}

		if (m != i) {
			swap(data, i, m);
			heapify(data, len, m, max);
		}
	}

	protected void _sort(T[] data, int len, boolean max) {
		int tmpLen = len;
		for (int i = len - 1; i > 0; i--) {
			swap(data, 0, i);
			tmpLen--;
			heapify(data, tmpLen, 0, max);
		}
	}

	protected int left(T[] data, int i) {
		return 2 * (i + 1) - 1;
	}

	protected int right(T[] data, int i) {
		return 2 * (i + 1);
	}

	protected void swap(T[] data, int i, int j) {
		T t = data[i];
		data[i] = data[j];
		data[j] = t;
	}

	protected void printr(T[] data, int len) {
		_printr(data, len, 0, 0);
		System.out.println();
	}

	protected void _printr(T[] data, int len, int index, int indent) {
		if (index > len - 1) {
			return;
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < indent; i++) {
			sb.append("-");
		}
		sb.append(data[index]);
		System.out.println(sb.toString());
		_printr(data, len, left(data, index), indent + 2);
		_printr(data, len, right(data, index), indent + 2);
	}
}
